nums = ['aaa', '123', '$%^', '*&fdk234']
numIndexList = list(range(len(nums)))
maxIndex = numIndexList[-1]

resultStack = []

def FindNextNum(n):
    global numIndexList
    if len(numIndexList) == 0:
        return False, -1

    for i in range(n + 1, maxIndex + 1):
        if i in numIndexList:
            return True, i

    return False, -1

def CheckBacktrack():
    global resultStack
    
    n = resultStack[-1]
    flag = False

    return FindNextNum(n)

def GiveItBack(idx):
    global numIndexList
    if len(numIndexList) == 0:
        numIndexList.append(idx)
    elif idx > max(numIndexList):
        numIndexList.append(idx)
    elif idx < min(numIndexList):
        numIndexList.insert(0, idx)
    else:
        for i in range(len(numIndexList)):
            if idx > numIndexList[i] and idx < numIndexList[i + 1]:
                numIndexList.insert(i + 1, idx)
                
def OutputResult(resultStack):
    result = []
    for item in resultStack:
        result.append(nums[item])

    print(result)

count = 0

def main():
    global numIndexList, count

    while True:
        if len(numIndexList) > 0:
            resultStack.append(numIndexList[0])
            numIndexList = numIndexList[1:]
        else:
            # 找到一组解
            OutputResult(resultStack)
            count += 1
            while True:
                flag, next_n = CheckBacktrack()
                if flag == True:
                    m = resultStack.pop()
                    resultStack.append(next_n)
                    numIndexList.remove(next_n)
                    GiveItBack(m)
                    break
                else:
                    m = resultStack.pop()
                    GiveItBack(m)
                    if len(resultStack) == 0:
                        # finished!
                        print("count = ", count)
                        return


main()
